package greedy_algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 使用HashMap保存电台和覆盖城市的关系。覆盖城市中不会有重复的值因此选用HashSet
        HashMap<String, HashSet<String>> info = new HashMap<>();

        // 创建各个电台所对应的覆盖城市
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        info.put("k1", hashSet1);
        info.put("k2", hashSet2);
        info.put("k3", hashSet3);
        info.put("k4", hashSet4);
        info.put("k5", hashSet5);

        // 使用allAreas记录所有当前还未被覆盖的城市
        List<String> allAreas = new ArrayList<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        // 使用selects记录选择电台的集合
        HashSet<String> selects = new HashSet<>();

        // 使用tmpSet记录电台覆盖的城市和还未被覆盖的城市的交集
        HashSet<String> tmpSet;

        // 使用maxKey记录最大覆盖电台
        String maxKey;

        while (allAreas.size() > 0) {
            maxKey = null;
            for (String key : info.keySet()) {
                tmpSet = info.get(key);
                tmpSet.retainAll(allAreas); // 求交集
                if (tmpSet.size() > 0 && (maxKey == null || tmpSet.size() > info.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                // 需要将allAreas中已被覆盖的城市删除
                allAreas.removeAll(info.get(maxKey));
            }
        }

        System.out.println(selects);
    }
}
